home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d3 / ddjhptxt.arc / STEVENS.LST < prev    next >
File List  |  1990-06-05  |  19KB  |  671 lines
  1. LISTING ONE
  2.  
  3. /* ---------- hyprtree.h --------- */
  4.  
  5. #define NODELEN 256         /* length of a node   */
  6. #define MAXLEVELS 10        /* tree levels        */
  7. #define MAXKEYLENGTH 25     /* maximum key length */
  8.  
  9. #define TRUE 1
  10. #define FALSE !TRUE
  11.  
  12. #define KSPACE (NODELEN-sizeof(NODEHDR))
  13. #define HYPERTREE "hyprtree.ndx"
  14.  
  15. /* ----- computes length of a key in a node -------- */
  16. #define keylength(nd,kp) (strlen(kp) + 1 + \
  17.     ((nd).nodehdr.isleaf?sizeof(KEYVALUE):sizeof(NODEPOINTER)))
  18.  
  19. /* ---------- node pointers and key values ---------- */
  20. typedef long KEYVALUE;
  21. typedef int NODEPOINTER;
  22.  
  23. typedef union {
  24.     KEYVALUE keyvalue;
  25.     NODEPOINTER nodepointer;
  26. } KEYPOINTER;
  27.  
  28. /* ---------- header record for a hypertree ---------- */
  29. typedef struct {
  30.     NODEPOINTER rootnode;
  31. } TREEHDR;
  32.  
  33. /* ---- header structure for a hypertree node -------- */
  34. typedef struct  {
  35.     int isleaf;         /* true if the node is a leaf */
  36.     NODEPOINTER parent; /* node number of parent */
  37.     KEYPOINTER lower;   /* keys < this node (or value if leaf)*/
  38. } NODEHDR;
  39.  
  40. /* --------- node record for a hypertree ---------- */
  41. typedef struct {
  42.     NODEHDR nodehdr;
  43.     char keys[KSPACE];
  44. } TREENODE;
  45.  
  46. /* ------------- prototypes --------------- */
  47. void addkey(char *key, KEYVALUE keyvalue);
  48. int findkey(char *key);
  49. int firstkey(void);
  50. int lastkey(void);
  51. int nextkey(void);
  52. int prevkey(void);
  53. KEYVALUE current_keyvalue(void);
  54. char *current_keystring(void);
  55.  
  56.  
  57. LISTING TWO
  58.  
  59. /* ---------------- addkey.c -------------- */
  60.  
  61. #include <stdio.h>
  62. #include <stdlib.h>
  63. #include <string.h>
  64. #include "hyprtree.h"
  65.  
  66. static void addkeyentry(int level, char *key,
  67.                 KEYPOINTER keypointer, NODEPOINTER lowernode);
  68. static void nullnode(int level);
  69. static int freespace(TREENODE node);
  70. static void writenode(int level);
  71. static void adopt(NODEPOINTER child, NODEPOINTER parent);
  72.  
  73. static TREENODE *nodes[MAXLEVELS];
  74. static NODEPOINTER nodenbr[MAXLEVELS];
  75. static NODEPOINTER nextnode;
  76.  
  77. static FILE *htree;
  78. static TREEHDR th;
  79.  
  80. /*
  81.  *  Add a key string value and its associated KEYVALUE to
  82.  * the hypertree.
  83.  */
  84. void addkey(char *key, KEYVALUE keyvalue)
  85. {
  86.     KEYPOINTER keypointer;
  87.     if (key == NULL)    {
  88.         /* ------ terminal key, complete the tree ------ */
  89.         if (htree != NULL)  {
  90.             int level = 0;
  91.             /* -------- write the unwritten nodes -------- */
  92.             while (nodes[level] != NULL)    {
  93.                 writenode(level);
  94.                 free(nodes[level]);
  95.                 level++;
  96.             }
  97.             /* ------ update the header block ---------- */
  98.             th.rootnode = nodenbr[level-1];
  99.             fseek(htree, 0L, SEEK_SET);
  100.             fwrite(&th, sizeof(TREEHDR), 1, htree);
  101.  
  102.             fclose(htree);
  103.         }
  104.     }
  105.     else    {
  106.         keypointer.keyvalue = keyvalue;
  107.         if (strlen(key) <= MAXKEYLENGTH)
  108.             addkeyentry(0, key, keypointer, 0);
  109.     }
  110. }
  111.  
  112. static void addkeyentry(int level, char *key,
  113.                 KEYPOINTER keypointer, NODEPOINTER lowernode)
  114. {
  115.     char *kp;
  116.  
  117.     if (nodes[level] == NULL)   {
  118.         /* -------- build a new node ---------- */
  119.         if (level == 0) {
  120.             /* ------ building a new tree ------ */
  121.             htree = fopen(HYPERTREE, "wb+");
  122.             /* ----- write a NULL header for now ----- */
  123.             fwrite(&th, sizeof(TREEHDR), 1, htree);
  124.         }
  125.         if ((nodes[level] = malloc(sizeof(TREENODE))) == NULL)  {
  126.             fputs("\nOut of memory!", stderr);
  127.             exit(1);
  128.         }
  129.         nodes[level+1] = NULL;
  130.         nullnode(level);
  131.         /* ---- point to the node of the lower keys --- */
  132.         nodes[level]->nodehdr.lower.nodepointer = lowernode;
  133.         /* --- assign the next node number to this node --- */
  134.         nodenbr[level] = ++nextnode;
  135.     }
  136.     if (keylength(*nodes[level],key) >
  137.             freespace(*nodes[level]))   {
  138.         /* -------- this node is full -------- */
  139.         KEYPOINTER keyp;
  140.         NODEPOINTER lowernode;
  141.         /* ---- write the node to the index file ---- */
  142.         writenode(level);
  143.         /* ---- remember the node nbr at this level ---- */
  144.         lowernode = nodenbr[level];
  145.         /* --- assign a new node number to this level --- */
  146.         nodenbr[level] = ++nextnode;
  147.         /* --- grow or add to parent with the current key --- */
  148.         memset(&keyp, 0, sizeof(KEYPOINTER));
  149.         keyp.nodepointer = nodenbr[level];
  150.         addkeyentry(level+1, key, keyp, lowernode);
  151.         /* - now set the node at this level to NULL values - */
  152.         nullnode(level);
  153.         nodes[level]->nodehdr.lower = keypointer;
  154.     }
  155.     else    {
  156.         /* ------ insert the key into the node ------ */
  157.         kp = nodes[level]->keys;
  158.         /* ----- scan to the end of the node ----- */
  159.         while (*kp)
  160.             kp += keylength(*nodes[level], kp);
  161.         strcpy(kp, key);
  162.         /* ----- attach the key pointer to the key ----- */
  163.         kp += strlen(kp)+1;
  164.         if (level == 0)
  165.             *((KEYVALUE *)kp) = keypointer.keyvalue;
  166.         else
  167.             *((NODEPOINTER *)kp) = keypointer.nodepointer;
  168.     }
  169. }
  170.  
  171. /* --------- build a null node ------------ */
  172. static void nullnode(int level)
  173. {
  174.     memset(nodes[level], 0, NODELEN);
  175.     nodes[level]->nodehdr.isleaf = level == 0;
  176. }
  177.  
  178. /* ------ compute space remaining in a node ------- */
  179. static int freespace(TREENODE node)
  180. {
  181.     int sp = KSPACE;
  182.     char *kp = node.keys;
  183.  
  184.     while (*kp) {
  185.         sp -= keylength(node,kp);
  186.         kp += keylength(node,kp);
  187.     }
  188.     return sp;
  189. }
  190.  
  191. /* ------ write a completed node ------- */
  192. static void writenode(int level)
  193. {
  194.     long where = (nodenbr[level]-1)*NODELEN+sizeof(TREEHDR);
  195.  
  196.     fseek(htree, where, SEEK_SET);
  197.     fwrite(nodes[level], NODELEN, 1, htree);
  198.     if (level)  {
  199.         /* - this is a parent node, update its children - */
  200.         char *kp = nodes[level]->keys;
  201.         adopt(nodes[level]->nodehdr.lower.nodepointer,
  202.                     nodenbr[level]);
  203.         while (*kp) {
  204.             adopt(*((NODEPOINTER *)(kp+strlen(kp)+1)),
  205.                     nodenbr[level]);
  206.             kp += keylength(*nodes[level], kp);
  207.         }
  208.     }
  209. }
  210.  
  211. /* ---- write a parent node number into a child node ---- */
  212. static void adopt(NODEPOINTER child, NODEPOINTER parent)
  213. {
  214.     NODEHDR nodehdr;
  215.     long here = ftell(htree);
  216.     long where = (child-1)*NODELEN+sizeof(TREEHDR);
  217.  
  218.     fseek(htree, where, SEEK_SET);
  219.     fread(&nodehdr, sizeof(NODEHDR), 1, htree);
  220.     nodehdr.parent = parent;
  221.     fseek(htree, where, SEEK_SET);
  222.     fwrite(&nodehdr, sizeof(NODEHDR), 1, htree);
  223.     fseek(htree, here, SEEK_SET);
  224. }
  225.  
  226.  
  227. LISTING THREE
  228.  
  229. /* ----------- srchtree.c ------------ */
  230.  
  231. #include <stdio.h>
  232. #include <stdlib.h>
  233. #include <string.h>
  234. #include "hyprtree.h"
  235.  
  236. /* ---------- search packet ----------- */
  237. typedef struct  {
  238.     NODEPOINTER node;
  239.     char *ky;
  240. } SEARCH;
  241.  
  242. FILE *htree;
  243. static TREEHDR th;
  244. static TREENODE node;
  245. static SEARCH current;
  246.  
  247. static void readnode(NODEPOINTER nodepointer);
  248. static void opentree(void);
  249.  
  250. /*
  251.  * Find a specified key in the tree.
  252.  * Return TRUE if found.
  253.  * Return FALSE if not found.
  254.  */
  255. int findkey(char *key)
  256. {
  257.     opentree();
  258.     if (th.rootnode)    {
  259.         SEARCH save = current;
  260.         readnode(th.rootnode);
  261.         while (TRUE)    {
  262.             int cmp;
  263.             current.ky = node.keys;
  264.             while (*current.ky) {
  265.                 cmp = stricmp(key, current.ky);
  266.                 if (cmp < 0)    {
  267.                     save = current;
  268.                     break;
  269.                 }
  270.                 if (cmp == 0)
  271.                     return TRUE;
  272.                 current.ky += keylength(node, current.ky);
  273.             }
  274.             if (!node.nodehdr.isleaf)   {
  275.                 if (current.ky == node.keys)
  276.                     readnode(node.nodehdr.lower.nodepointer);
  277.                 else
  278.                     readnode(*((NODEPOINTER *)
  279.                         (current.ky-sizeof(NODEPOINTER))));
  280.             }
  281.             else    {
  282.                 current = save;
  283.                 readnode(current.node);
  284.                 break;
  285.             }
  286.         }
  287.     }
  288.     return FALSE;
  289. }
  290.  
  291. /*
  292.  * Find the first sequential key in the tree.
  293.  * Return TRUE if found.
  294.  * Return FALSE if not found (the tree is empty).
  295.  */
  296. int firstkey(void)
  297. {
  298.     opentree();
  299.     if (th.rootnode)    {
  300.         readnode(th.rootnode);
  301.         while (!node.nodehdr.isleaf)
  302.             readnode(node.nodehdr.lower.nodepointer);
  303.         current.ky = node.keys;
  304.         return TRUE;
  305.     }
  306.     return FALSE;
  307. }
  308.  
  309. /*
  310.  * Find the last sequential key in the tree.
  311.  * Return TRUE if found.
  312.  * Return FALSE if not found (the tree is empty).
  313.  */
  314. int lastkey(void)
  315. {
  316.     NODEPOINTER np;
  317.     opentree();
  318.     if (th.rootnode)    {
  319.         int len = 0;
  320.         np = th.rootnode;
  321.         current.node = th.rootnode;
  322.         current.ky = node.keys;
  323.         do  {
  324.             SEARCH save = current;
  325.             readnode(np);
  326.             current.ky = node.keys;
  327.             while (*current.ky) {
  328.                 len = keylength(node, current.ky);
  329.                 current.ky += len;
  330.             }
  331.             if (current.ky == node.keys)    {
  332.                 readnode(save.node);
  333.                 current.ky = save.ky;
  334.                 break;
  335.             }
  336.             else
  337.                 np = *((NODEPOINTER *)
  338.                     (current.ky-sizeof(NODEPOINTER)));
  339.         } while (!node.nodehdr.isleaf);
  340.         current.ky -= len;
  341.         return TRUE;
  342.     }
  343.     return FALSE;
  344. }
  345.  
  346. /*
  347.  * Find the next sequential key in the tree.
  348.  * Return TRUE if found.
  349.  * Return FALSE if not found (the tree is empty or at the end).
  350.  */
  351. int nextkey(void)
  352. {
  353.     opentree();
  354.     if (th.rootnode)    {
  355.         if (current.ky == NULL)
  356.             return firstkey();
  357.         current.ky += keylength(node, current.ky);
  358.         if (!node.nodehdr.isleaf)   {
  359.             readnode(*((NODEPOINTER *)
  360.                     (current.ky-sizeof(NODEPOINTER))));
  361.             current.ky = node.keys;
  362.             while (!node.nodehdr.isleaf)
  363.                 readnode(node.nodehdr.lower.nodepointer);
  364.         }
  365.         /* ----- while at the end of a node ------ */
  366.         while (*current.ky == '\0') {
  367.             NODEPOINTER child = current.node;
  368.             if (node.nodehdr.parent == 0)
  369.                 break;
  370.             readnode(node.nodehdr.parent);
  371.             current.ky = node.keys;
  372.             if (child == node.nodehdr.lower.nodepointer)
  373.                 break;
  374.             while (*current.ky) {
  375.                 NODEPOINTER this = *((NODEPOINTER *)
  376.                     (current.ky+strlen(current.ky)+1));
  377.                 current.ky += keylength(node, current.ky);
  378.                 if (this == child)
  379.                     break;
  380.             }
  381.         }
  382.         return *current.ky != '\0';
  383.     }
  384.     return FALSE;
  385. }
  386.  
  387. /*
  388.  * Find the previous sequential key in the tree.
  389.  * Return TRUE if found.
  390.  * Return FALSE if not found
  391.  * (the tree is empty or at the beginning).
  392.  */
  393. int prevkey(void)
  394. {
  395.     char *kp;
  396.     opentree();
  397.     if (th.rootnode)    {
  398.         if (current.ky == NULL)
  399.             return lastkey();
  400.         if (!node.nodehdr.isleaf)   {
  401.             /* ----- navigate to end of the lower leaf ----- */
  402.             NODEPOINTER np;
  403.             if (current.ky == node.keys)
  404.                 np = node.nodehdr.lower.nodepointer;
  405.             else
  406.                 np = *((NODEPOINTER *)
  407.                     (current.ky-sizeof(NODEPOINTER)));
  408.             while (!node.nodehdr.isleaf)    {
  409.                 readnode(np);
  410.                 current.ky = node.keys;
  411.                 while (*current.ky)
  412.                     current.ky += keylength(node, current.ky);
  413.                 np = *((NODEPOINTER *)
  414.                     (current.ky-sizeof(NODEPOINTER)));
  415.             }
  416.         }
  417.         /* ----- while at the beginning of a node ------ */
  418.         while (current.ky == node.keys) {
  419.             NODEPOINTER child = current.node;
  420.             if (node.nodehdr.parent == 0)
  421.                 break;
  422.             readnode(node.nodehdr.parent);
  423.             current.ky = node.keys;
  424.             if (child == node.nodehdr.lower.nodepointer)
  425.                 continue;
  426.  
  427.             while (*current.ky) {
  428.                 NODEPOINTER this = *((NODEPOINTER *)
  429.                     (current.ky+strlen(current.ky)+1));
  430.                 current.ky += keylength(node, current.ky);
  431.                 if (this == child)
  432.                     break;
  433.             }
  434.         }
  435.         /* -------- go to previous key in node -------- */
  436.         if (current.ky != node.keys)    {
  437.             kp = node.keys;
  438.             while (kp+keylength(node, kp) < current.ky)
  439.                 kp += keylength(node, kp);
  440.             current.ky = kp;
  441.             return TRUE;
  442.         }
  443.     }
  444.     return FALSE;
  445. }
  446.  
  447. /*
  448.  * Return the key value associated with the most recently
  449.  * retrieved key.
  450.  */
  451. KEYVALUE current_keyvalue(void)
  452. {
  453.     KEYVALUE rtn;
  454.     if (!node.nodehdr.isleaf)   {
  455.         SEARCH save = current;
  456.         current.ky += keylength(node, current.ky);
  457.         while (!node.nodehdr.isleaf)    {
  458.             NODEPOINTER np;
  459.             if (current.ky == node.keys)
  460.                 np = node.nodehdr.lower.nodepointer;
  461.             else
  462.                 np = *((NODEPOINTER *)
  463.                     (current.ky-sizeof(NODEPOINTER)));
  464.             readnode(np);
  465.             current.ky = node.keys;
  466.         }
  467.         rtn = node.nodehdr.lower.keyvalue;
  468.         current = save;
  469.         readnode(save.node);
  470.         return rtn;
  471.     }
  472.     return *((KEYVALUE *)(current.ky+strlen(current.ky)+1));
  473. }
  474.  
  475. /*
  476.  * Return the key string value of the most recently
  477.  * retrieved key.
  478.  */
  479. char *current_keystring(void)
  480. {
  481.     return current.ky;
  482. }
  483.  
  484. /* -------- open the tree ----------- */
  485. static void opentree(void)
  486. {
  487.     if (htree == NULL)  {
  488.         if ((htree = fopen(HYPERTREE, "rb")) == NULL)   {
  489.             fputs("\n" HYPERTREE " not found", stderr);
  490.             exit(1);
  491.         }
  492.         fread(&th, sizeof(TREEHDR), 1, htree);
  493.     }
  494. }
  495.  
  496. /* ---------- read a specified node ------------- */
  497. static void readnode(NODEPOINTER nodepointer)
  498. {
  499.     long where = (nodepointer-1)*NODELEN+sizeof(TREEHDR);
  500.  
  501.     fseek(htree, where, SEEK_SET);
  502.     fread(&node, NODELEN, 1, htree);
  503.     current.node = nodepointer;
  504. }
  505.  
  506.  
  507. LISTING FOUR
  508.  
  509. /* -------- keyextr.c ---------- */
  510.  
  511. /*
  512.  * Build a test HyperTree from standard input.
  513.  * <> delimiters define the key values.
  514.  * This is pass one, which builds the sortable table.
  515.  */
  516.  
  517. #include <stdio.h>
  518. #include <string.h>
  519. #include "hyprtree.h"
  520.  
  521. #define KEYTOKEN '<'
  522. #define TERMINAL '>'
  523. #define QUOTE    '"'
  524. #define ESCAPE   '\\'
  525.  
  526. void main(void)
  527. {
  528.     int c;
  529.     while ((c = getchar()) != EOF)  {
  530.         if (c == KEYTOKEN)  {
  531.             long fileposition = ftell(stdin)-1;
  532.             int counter = 0;
  533.             putchar(QUOTE);
  534.             while ((c = getchar()) != TERMINAL) {
  535.                 if (c == EOF || counter++ == MAXKEYLENGTH)
  536.                     break;
  537.                 if (c == QUOTE)
  538.                     putchar(ESCAPE);
  539.                 putchar(c);
  540.             }
  541.             putchar(QUOTE);
  542.             putchar(',');
  543.             printf("%ld\n", fileposition);
  544.         }
  545.     }
  546. }
  547.  
  548.  
  549. LISTING FIVE
  550.  
  551. /* ----------- keybuild.c ----------- */
  552.  
  553. /*
  554.  * Build a test HyperTree from standard input.
  555.  * This is pass three, which builds the HyperTree
  556.  * from the sorted table.
  557.  */
  558.  
  559. #include <stdio.h>
  560. #include <string.h>
  561. #include <stdlib.h>
  562. #include "hyprtree.h"
  563.  
  564. #define QUOTE    '"'
  565. #define ESCAPE   '\\'
  566.  
  567. void main(void)
  568. {
  569.     int c;
  570.     char key[MAXKEYLENGTH+1];
  571.     char kv[20];
  572.     KEYVALUE keyvalue;
  573.  
  574.     while ((c = getchar()) != EOF)  {
  575.         if (c == QUOTE) {
  576.             int counter = 0;
  577.             char *cp = key;
  578.             while ((c = getchar()) != QUOTE)    {
  579.                 if (c == EOF || counter++ == MAXKEYLENGTH)
  580.                     break;
  581.                 if (c == ESCAPE)
  582.                     c = getchar();
  583.                 *cp++ = c;
  584.             }
  585.             *cp = '\0';
  586.             if (getchar() == ',')   {
  587.                 char *kp = kv;
  588.                 while ((c = getchar()) != '\n' && c != EOF)
  589.                     *kp++ = c;
  590.                 *kp = '\0';
  591.                 keyvalue = atol(kv);
  592.                 addkey(key, keyvalue);
  593.             }
  594.         }
  595.     }
  596.     addkey(NULL, keyvalue);
  597. }
  598.  
  599.  
  600. LISTING SIX
  601.  
  602. /* ------------- hyprsrch.c -------------- */
  603.  
  604. /*
  605.  * Search the test HyperTree for a match on the
  606.  * command-line parameter.
  607.  * Display a screen of text starting at the
  608.  * position indicated for the matching (or closest)
  609.  * entry in the HyperTree.
  610.  */
  611.  
  612. #include <stdio.h>
  613. #include <string.h>
  614. #include <ctype.h>
  615. #include <conio.h>
  616. #include "hyprtree.h"
  617.  
  618. #define SCRLINES 25
  619.  
  620. void main(int argc, char *argv[])
  621. {
  622.     if (argc < 3)
  623.         fprintf(stderr, "Usage: hyprsrch textfile keyvalue");
  624.     else    {
  625.         int kb = 0;
  626.         FILE *fp = fopen(argv[1], "r");
  627.         if (fp == NULL) {
  628.             fprintf(stderr, "No such file as %s", argv[1]);
  629.             return;
  630.         }
  631.         findkey(argv[2]);
  632.         while (toupper(kb) != 'Q')  {
  633.             int lc = 4, c;
  634.             KEYVALUE kv = current_keyvalue();
  635.             printf("\n%s (%ld)", current_keystring(), kv);
  636.             printf("\n------------------------------------\n");
  637.             if (kv) {
  638.                 fseek(fp, kv, SEEK_SET);
  639.                 while ((c = getc(fp)) != EOF && lc < SCRLINES){
  640.                     if (c == '\n')
  641.                         lc++;
  642.                     putchar(c);
  643.                 }
  644.             }
  645.             printf("\nF = first, "
  646.                      "L = last, "
  647.                      "N = next, "
  648.                      "P = previous, "
  649.                      "Q = quit...");
  650.             kb = getch();
  651.             switch (toupper(kb))    {
  652.                 case 'F':
  653.                     firstkey();
  654.                     break;
  655.                 case 'L':
  656.                     lastkey();
  657.                     break;
  658.                 case 'N':
  659.                     nextkey();
  660.                     break;
  661.                 case 'P':
  662.                     prevkey();
  663.                     break;
  664.                 default:
  665.                     break;
  666.             }
  667.         }
  668.     }
  669. }
  670.  
  671.